import javafx.geometry.Pos;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-24
 * Time: 20:52
 */
class Position{
    public int x;
    public int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        // 先找到所有腐烂的橘子作为起点, 即作为第一层
        Queue<Position> queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j] == 2){
                    queue.add(new Position(i, j));
                }
            }
        }
        int count = 0;
        int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()){
            int size = queue.size();
            // 腐蚀一层
            boolean flag = false; // 标记这一层是否腐蚀新的橘子
            for (int i = 0; i < size; i++) {
                Position position = queue.poll();
                // 扫描腐烂的橘子的上下左右四个方向, 并进行腐蚀
                for (int j = 0; j < 4; j++) {
                    // 注意这里是 j, 不要顺手写成 j
                    int x = position.x + next[j][0];
                    int y  = position.y + next[j][1];
                    // 不符合条件就不添加
                    if(x < 0 || x >= row || y < 0 || y >= col || grid[x][y] != 1){
                        continue;
                    }
                    // 腐烂掉
                    grid[x][y] = 2;
                    flag = true;
                    queue.add(new Position(x, y));
                }
            }
            // 这一层腐蚀新的橘子之后再 ++
            if(flag){
                count++;
            }
        }
        // 如果还有橘子没有被腐蚀, 那么说明就不能完全腐蚀掉所有的橘子
        for (int[] ints : grid) {
            for (int x: ints) {
                if(x == 1){
                    count = -1;
                }
            }
        }
        return count;
    }
}